//      suffix_array.h
//      
//      Copyright 2012 tqlong <tqlong@espada>
//      
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of the GNU General Public License as published by
//      the Free Software Foundation; either version 2 of the License, or
//      (at your option) any later version.
//      
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.
//      
//      You should have received a copy of the GNU General Public License
//      along with this program; if not, write to the Free Software
//      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
//      MA 02110-1301, USA.

#ifndef SUFFIX_ARRAY_H
#define SUFFIX_ARRAY_H

#include <vector>
#include <string>
#include <algorithm>

#include "dna_processing.h"

class SuffixArray
{
  static std::string temp;
 public:
  SuffixArray(std::string& s);
 SuffixArray() : s_(temp) {}

  bool operator() (int i, int j) const;
  int count(const std::string& sub) const;

  std::ostream& print (std::ostream&o, bool isFile = false) const;

  const SuffixArray& operator=(SuffixArray& sa) {
    s_ = sa.s_; 
    order_ = sa.order_;
    return *this;
  }
 protected:
  void build_array();
  int find_left(const std::string& sub) const;
  int find_right(const std::string& sub) const;

  std::string& s_;
  std::vector<int> order_;
};

class SequencesSA : public std::vector<SuffixArray>
{
 public:
  SequencesSA(Sequences& seqs);

  int count(const std::string& sub) const;
 protected:
  Sequences& seqs_;
};

#endif
